home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / arc.zoo / arcsqs.c < prev    next >
C/C++ Source or Header  |  1989-01-29  |  12KB  |  469 lines
  1. /*
  2.  * $Header: arcsqs.c,v 1.3 88/07/31 18:54:14 hyc Exp $
  3.  */
  4.  
  5. /*  ARC - Archive utility - SQUASH
  6.  
  7. (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
  8.  
  9.  This is a quick hack to ARCLZW to make it handle squashed archives.
  10.  Dan Lanciani (ddl@harvard.*) July 87
  11.  
  12. */
  13.  
  14. /*
  15.  * $Header: arcsqs.c,v 1.3 88/07/31 18:54:14 hyc Exp $
  16.  */
  17.  
  18. #include <stdio.h>
  19. #include "arc.h"
  20.  
  21. #if    MSDOS
  22. char    *setmem();
  23. #else
  24. #ifndef __STDC__
  25. char    *memset();
  26. #endif
  27. #endif
  28. int    getc_unp();
  29. void    putc_pak(), putc_unp();
  30. static void    putcode();
  31.  
  32. /* definitions for the new dynamic Lempel-Zev crunching */
  33.  
  34. #define BITS   13        /* maximum bits per code */
  35. #define HSIZE  10007        /* 80% occupancy */
  36. #define INIT_BITS 9        /* initial number of bits/code */
  37. static int      n_bits;        /* number of bits/code */
  38. static int      maxcode;    /* maximum code, given n_bits */
  39. #define MAXCODE(n)      ((1<<(n)) - 1)    /* maximum code calculation */
  40. static int      maxcodemax = 1 << BITS;    /* largest possible code (+1) */
  41.  
  42. static unsigned char buf[BITS];    /* input/output buffer */
  43.  
  44. static unsigned char lmask[9] =    /* left side masks */
  45. {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
  46. static unsigned char rmask[9] =    /* right side masks */
  47. {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  48.  
  49. static int      offset;        /* byte offset for code output */
  50. static long     in_count;    /* length of input */
  51. static long     bytes_out;    /* length of compressed output */
  52. static unsigned short ent;
  53.  
  54. long     htab[HSIZE];    /* hash code table   (crunch) */
  55. unsigned short codetab[HSIZE];    /* string code table (crunch) */
  56.  
  57. static unsigned short *prefix = codetab;  /* prefix code table (uncrunch) */
  58. static unsigned char *suffix=(unsigned char *)htab;  /* suffix table (uncrunch) */
  59. static int      free_ent;    /* first unused entry */
  60. static int      firstcmp;    /* true at start of compression */
  61. unsigned char stack[HSIZE];    /* local push/pop stack */
  62.  
  63. /*
  64.  * block compression parameters -- after all codes are used up,
  65.  * and compression rate changes, start over.
  66.  */
  67.  
  68. static int      clear_flg;
  69. static long     ratio;
  70. #define CHECK_GAP 10000        /* ratio check interval */
  71. static long     checkpoint;
  72.  
  73. /*
  74.  * the next two codes should not be changed lightly, as they must not
  75.  * lie within the contiguous general code space.
  76.  */
  77. #define FIRST   257        /* first free entry */
  78. #define CLEAR   256        /* table clear output code */
  79.  
  80. static void
  81. cl_block(t)            /* table clear for block compress */
  82.     FILE           *t;    /* our output file */
  83. {
  84.     long            rat;
  85.  
  86.     checkpoint = in_count + CHECK_GAP;
  87.  
  88.     if (in_count > 0x007fffffL) {    /* shift will overflow */
  89.         rat = bytes_out >> 8;
  90.         if (rat == 0)    /* Don't divide by zero */
  91.             rat = 0x7fffffffL;
  92.         else
  93.             rat = in_count / rat;
  94.     } else
  95.         rat = (in_count << 8) / bytes_out;    /* 8 fractional bits */
  96.  
  97.     if (rat > ratio)
  98.         ratio = rat;
  99.     else {
  100.         ratio = 0;
  101.         setmem(htab, HSIZE * sizeof(long), 0xff);
  102.         free_ent = FIRST;
  103.         clear_flg = 1;
  104.         putcode(CLEAR, t);
  105.     }
  106. }
  107.  
  108. /*****************************************************************
  109.  *
  110.  * Output a given code.
  111.  * Inputs:
  112.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  113.  *              that n_bits =< (long)wordsize - 1.
  114.  * Outputs:
  115.  *      Outputs code to the file.
  116.  * Assumptions:
  117.  *      Chars are 8 bits long.
  118.  * Algorithm:
  119.  *      Maintain a BITS character long buffer (so that 8 codes will
  120.  * fit in it exactly).  When the buffer fills up empty it and start over.
  121.  */
  122.  
  123. static void
  124. putcode(code, t)        /* output a code */
  125.     int             code;    /* code to output */
  126.     FILE           *t;    /* where to put it */
  127. {
  128.     int             r_off = offset;    /* right offset */
  129.     int             bits = n_bits;    /* bits to go */
  130.     unsigned char  *bp = buf;    /* buffer pointer */
  131.     int             n;    /* index */
  132.     register int    ztmp;
  133.  
  134.     if (code >= 0) {    /* if a real code *//* Get to the first byte. */
  135.         bp += (r_off >> 3);
  136.         r_off &= 7;
  137.  
  138.         /*
  139.          * Since code is always >= 8 bits, only need to mask the
  140.          * first hunk on the left. 
  141.          */
  142.         ztmp = (code << r_off) & lmask[r_off];
  143.         *bp = (*bp & rmask[r_off]) | ztmp;
  144.         bp++;
  145.         bits -= (8 - r_off);
  146.         code >>= (8 - r_off);
  147.  
  148.         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  149.         if (bits >= 8) {
  150.             *bp++ = code;
  151.             code >>= 8;
  152.             bits -= 8;
  153.         }
  154.         /* Last bits. */
  155.         if (bits)
  156.             *bp = code;
  157.  
  158.         offset += n_bits;
  159.  
  160.         if (offset == (n_bits << 3)) {
  161.             bp = buf;
  162.             bits = n_bits;
  163.             bytes_out += bits;
  164.             do
  165.                 putc_pak(*bp++, t);
  166.             while (--bits);
  167.             offset = 0;
  168.         }
  169.         /*
  170.          * If the next entry is going to be too big for the code
  171.          * size, then increase it, if possible. 
  172.          */
  173.         if (free_ent > maxcode || clear_flg > 0) {    /* Write the whole
  174.                                  * buffer, because the
  175.                                  * input side won't
  176.                                  * discover the size
  177.                                  * increase until after
  178.                                  * it has read it. */
  179.             if (offset > 0) {
  180.                 bp = buf;    /* reset pointer for writing */
  181.                 bytes_out += n = n_bits;
  182.                 while (n--)
  183.                     putc_pak(*bp++, t);
  184.             }
  185.             offset = 0;
  186.  
  187.             if (clear_flg) {    /* reset if clearing */
  188.                 maxcode = MAXCODE(n_bits = INIT_BITS);
  189.                 clear_flg = 0;
  190.             } else {/* else use more bits */
  191.                 n_bits++;
  192.                 if (n_bits == BITS)
  193.                     maxcode = maxcodemax;
  194.                 else
  195.                     maxcode = MAXCODE(n_bits);
  196.             }
  197.         }
  198.     } else {        /* dump the buffer on EOF */
  199.         bytes_out += n = (offset + 7) / 8;
  200.  
  201.         if (offset > 0)
  202.             while (n--)
  203.                 putc_pak(*bp++, t);
  204.         offset = 0;
  205.     }
  206. }
  207.  
  208. /*****************************************************************
  209.  *
  210.  * Read one code from the standard input.  If EOF, return -1.
  211.  * Inputs:
  212.  *      cmpin
  213.  * Outputs:
  214.  *      code or -1 is returned.
  215.  */
  216.  
  217. static int
  218. getcode(f)            /* get a code */
  219.     FILE           *f;    /* file to get from */
  220. {
  221.     int             code;
  222.     static int      offset = 0, size = 0;
  223.     int             r_off, bits;
  224.     unsigned char  *bp = buf;
  225.  
  226.     if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
  227.         /* If the next entry will be too big for the current code
  228.          * size, then we must increase the size. This implies reading
  229.          * a new buffer full, too. */
  230.         if (free_ent > maxcode) {
  231.             n_bits++;
  232.             if (n_bits == BITS)
  233.                 maxcode = maxcodemax;    /* won't get any bigger
  234.                              * now */
  235.             else
  236.                 maxcode = MAXCODE(n_bits);
  237.         }
  238.         if (clear_flg > 0) {
  239.             maxcode = MAXCODE(n_bits = INIT_BITS);
  240.             clear_flg = 0;
  241.         }
  242.         for (size = 0; size < n_bits; size++) {
  243.             if ((code = getc_unp(f)) == EOF)
  244.                 break;
  245.             else
  246.                 buf[size] = code;
  247.         }
  248.         if (size <= 0)
  249.             return -1;    /* end of file */
  250.  
  251.         offset = 0;
  252.         /* Round size down to integral number of codes */
  253.         size = (size << 3) - (n_bits - 1);
  254.     }
  255.     r_off = offset;
  256.     bits = n_bits;
  257.  
  258.     /*
  259.      * Get to the first byte. 
  260.      */
  261.     bp += (r_off >> 3);
  262.     r_off &= 7;
  263.  
  264.     /* Get first part (low order bits) */
  265.     code = (*bp++ >> r_off);
  266.     bits -= 8 - r_off;
  267.     r_off = 8 - r_off;    /* now, offset into code word */
  268.  
  269.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  270.     if (bits >= 8) {
  271.         code |= *bp++ << r_off;
  272.         r_off += 8;
  273.         bits -= 8;
  274.     }
  275.     /* high order bits. */
  276.     code |= (*bp & rmask[bits]) << r_off;
  277.     offset += n_bits;
  278.  
  279.     return code;
  280. }
  281.  
  282. /*
  283.  * compress a file
  284.  *
  285.  * Algorithm:  use open addressing double hashing (no chaining) on the
  286.  * prefix code / next character combination.  We do a variant of Knuth's
  287.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  288.  * secondary probe.  Here, the modular division first probe is gives way
  289.  * to a faster exclusive-or manipulation.  Also do block compression with
  290.  * an adaptive reset, where the code table is cleared when the compression
  291.  * ratio decreases, but after the table fills.  The variable-length output
  292.  * codes are re-sized at this point, and a special CLEAR code is generated
  293.  * for the decompressor.
  294.  */
  295.  
  296. void
  297. sqinit_cm()            /* initialize for compression */
  298. {
  299.     offset = 0;
  300.     bytes_out = 0;
  301.     clear_flg = 0;
  302.     ratio = 0;
  303.     in_count = 1;
  304.     checkpoint = CHECK_GAP;
  305.     maxcode = MAXCODE(n_bits = INIT_BITS);
  306.     free_ent = FIRST;
  307.     setmem(htab, HSIZE * sizeof(long), 0xff);
  308.     n_bits = INIT_BITS;    /* set starting code size */
  309.  
  310.     firstcmp = 1;        /* next byte will be first */
  311. }
  312.  
  313. void
  314. sqputc_cm(c, t)            /* compress a character */
  315.     unsigned char   c;    /* character to compress */
  316.     FILE           *t;    /* where to put it */
  317. {
  318.     static long